\subsection{A* search} \label{sec:A star search}
A* keeps a sorted priority queue of alternate path segments along the way, denoted ... in the below code.

\subsubsection{Representation}
As it can be seen in the above pseudocode a different notation than in the previous Dijkstra is used. This notation is explained below.
\begin{itemize}
\item Previous$[$ $]$: map of previously navigated vertices.
\item g$[$source$]$: cost from start along best known path. In Dijkstra we refer to this as dist[source].
\item h(source, target): The heuristic function estimating total cost from source to target through y.
\item u: current vertex
\item v: a neighbour vertices of u.
\item alt$\_$g$[v]$: alternative best edge with lowest cost to the neighbour vertice 'v'.
\item dist$\_$between$[u,v]$: function that calculates returns the distance between current vertex u and neighbor v. 
\item reconstruct$\_$path(Previous$[]$, u)
\end{itemize}

\begin{lstlisting}[caption=A* search algorithm, label={lst:A star search}]
function A*(source, target)
	S := empty  
	Q := {source}
	Previous[] := the empty map    
 
	g[source] := 0
	f[source] := g[source] + h(source, target)
 
	while Q is not empty
		u := the vertex in Q having the lowest f[n] value
		if u = target
			return reconstruct_path(Previous[], target)
 
		remove u from Q
		add u to S
		for each neighbor v of u
			alt_g[v] := g[u] + dist_between(u,v)
			if neighbor v in S and alt_g[v] >= g[v]
				continue
 
			if neighbor v not in Q or alt_g[v] < g[v] 
				Previous[v] := u
				g[v] := alt_g[v]
				f[v] := g[v] + h(v, target)
				if neighbor v not in Q
					add v to Q
 
	return failure
 
function reconstruct_path(Previous[], u)
	if u in Previous[]
		p := reconstruct_path(Previous[], Previous[u])
		return (p + u)
	else
		return u
\end{lstlisting}


\subsubsection{Heuristic}
The heuristic is what speeds up A* as it allows it to visit fewer vertices before reaching its target. There are different heuristic functions to be used depending on context, I.E. the domain. \\
The important part about the heuristic function is that it needs to be admissible, not just "approximate", meaning that it never overestimates the cost of reaching the target. \\
One example of a heuristic function is \textit{The Manhattan Method}, which will get to the target in the least steps. The Manhattan Method however is inadmissible and doesn't always guarantee the shortest path. \\
It can be calculated by: H(n) = abs(current.X-target.X) + abs(current.Y-target.Y), where abs returns the absolute value of the expression. \\
\textit{The Diagonal Shortcut} is another heuristic used.

\subsubsection{Running Time and Memory Usage}
The time complexity of A* depends on the heuristic function it uses. \\
The time complexity for Breadth-first search can be expressed as: O(|V| + |E|) since every vertex and edge will be visited.
It's it worth remembering that a graph can contain several edges for every vertex.
